#include"BSTree.h"
BSNode* CreatBST(KeyType arr[], int n)
{
	int i = 0;
	BSNode* bt = NULL;
	while (i < n)
	{
		bt = BSInsert(bt, arr[i]);
		i++;
	}
	return bt;
}
BSNode* BSInsert(BSNode* bt, KeyType x)
{
	BSNode* f, * p = bt;
	f = NULL;
	while (p != NULL)
	{
		f = p;
		if (p->Key > x)
		{
			p = p->_left;
		}
		if (p->Key < x)
		{
			p = p->_right;
		}
	}
	p = (BSNode*)malloc(sizeof(BSNode));
	p->Key = x;
	p->_left = p->_right = NULL;
	if (bt == NULL)
	{
		bt = p;
	}
	else if (x < f->Key)
	{
		f->_left = p;
	}
	else
	{
		f->_right = p;
	}
}
BSNode* BSTSearch(BSNode* bt, KeyType x)
{
	if (bt == NULL)
	{
		return NULL;
	}
	else
	{
		if (bt->Key == x)
		{
			return bt;
		}
		else if (bt->Key > x)
		{
			return 	BSTSearch(bt->_left, x);
		}
		else
		{
			return BSTSearch(bt->_right, x);
		}
	}
}